package com.mid;

/**
 * Created by Lxk on 2020/2/13.
 */
class WordDictionary {

    private static class Node {

        private char ch;

        private Node[] child;

        private boolean isEnd;

        public Node(char ch) {
            this.ch = ch;
        }

        public Node(char ch, boolean isEnd) {
            this.ch = ch;
            this.isEnd = isEnd;
        }
    }

    private Node[] root;


    /**
     * Initialize your data structure here.
     */
    public WordDictionary() {
        this.root = new Node[26];
    }

    /**
     * Adds a word into the data structure.
     */
    public void addWord(String word) {
        Node[] curArr = root;
        Node preNode = null;
        for (int pos = 0; pos < word.length(); pos++) {
            if (pos >= word.length()) {
                return;
            }
            if (curArr == null) {
                curArr = new Node[26];
                preNode.child = curArr;
            }
            //该字符位置为空
            if (curArr[word.charAt(pos) - 'a'] == null) {
                Node cur = new Node(word.charAt(pos));
                if (pos == word.length() - 1) {
                    cur.isEnd = true;
                }
                curArr[word.charAt(pos) - 'a'] = cur;
            } else {
                if (pos == word.length() - 1) {
                    curArr[word.charAt(pos) - 'a'].isEnd = true;
                }
            }
            preNode = curArr[word.charAt(pos) - 'a'];
            curArr = preNode.child;
        }
    }

    private boolean searchEach(int pos, String word, Node[] cur) {
        if (cur == null) {
            return false;
        }
        if (pos == word.length() - 1) {
            if (word.charAt(pos) == '.') {
                if (cur != null) {
                    for (int i = 0; i < 26; i++) {
                        if (cur[i] != null && cur[i].isEnd) {
                            return true;
                        }
                    }
                }
                return false;
            }
            if (cur[word.charAt(pos) - 'a'] != null && cur[word.charAt(pos) - 'a'].isEnd) {
                return true;
            } else {
                return false;
            }
        }
        if (word.charAt(pos) == '.') {
            for (int i = 0; i < 26; i++) {
                if (cur != null && cur[i] != null) {
                    boolean res = searchEach(pos + 1, word, cur[i].child);
                    if (res) {
                        return res;
                    }
                }
            }
            return false;
        } else {
            char ch = word.charAt(pos);
            if (cur != null && cur[ch - 'a'] != null) {
                return searchEach(pos + 1, word, cur[ch - 'a'].child);
            } else {
                return false;
            }
        }
    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        Node[] cur = root;
        return searchEach(0, word, cur);
    }

}


public class Solution211 {

    public static void main(String[] args) {
        WordDictionary dictionary = new WordDictionary();
        dictionary.addWord("at");
        dictionary.addWord("and");
        dictionary.addWord("an");
        dictionary.addWord("add");
        System.out.println(dictionary.search("a"));
        System.out.println(dictionary.search(".at"));
        dictionary.addWord("bat");
        System.out.println(dictionary.search(".at"));
        System.out.println(dictionary.search("an."));
        System.out.println(dictionary.search("a.d."));
        System.out.println(dictionary.search("b."));
        System.out.println(dictionary.search("a.d"));
        System.out.println(dictionary.search("."));
    }

}
